package com.mobile.framework.util;

import java.util.ArrayList;

import org.apache.commons.beanutils.PropertyUtils;

/**
 * TreeSort.
 */
public class TreeSort {

	// 排序用的主程序
	public static ArrayList sort(ArrayList treeList) {
		init(treeList);
		ArrayList treeAim = new ArrayList();
		Tree tree = new Tree();
		tree.setParentId(new Long(-2));
		tree.setId(new Long(-1));
		tree.setArrange(new Long(0));
		treeAim.add(tree);
		int index = -1;
		int temp = -1;
		Tree treeF = null;

		while (!treeList.isEmpty()) {
			for (int i = 0; i < treeList.size(); i++) {
				treeF = (Tree) treeList.get(i);
				index = findIndex(treeAim, treeF);
				temp = i;
				if (index >= 0) {
					setArray(treeAim, index, treeF);
					break;
				}
			}
			if (index >= 0 && temp >= 0) {
				removeArray(treeList, temp);
				temp = -1;
			}
		}

		revertArray(treeAim);
		return treeAim;
	}

	// 对返回的ArrayList做些还原处理
	private static void revertArray(ArrayList treeAim) {
		if (!treeAim.isEmpty()) {
			treeAim.remove(0);
		}
		Tree treeF = null;
		for (int i = 0; i < treeAim.size(); i++) {
			treeF = (Tree) treeAim.get(i);
			if (treeF.getParentId().longValue() == -1) {
				treeF.setParentId(treeF.getId());
				treeF.setArrange(new Long(1));
			}

			treeAim.set(i, treeF.getObject());
		}
	}

	// 将排好序的元素移除
	private static void removeArray(ArrayList treeList, int index) {
		if (!treeList.isEmpty()) {
			treeList.remove(index);
		}
	}

	// 将元素插入到指定的位置
	private static void setArray(ArrayList treeAim, int index, Tree tree) {
		if (index >= treeAim.size()) {
			treeAim.add(tree);
			return;
		}
		treeAim.add(treeAim.get(treeAim.size() - 1));
		for (int i = treeAim.size() - 1; i > index; i--) {
			treeAim.set(i, treeAim.get(i - 1));
		}
		treeAim.set(index, tree);
	}

	// 找到元素的位置,先排元素的父类元素,如果父元素还没排则该元素先不排
	private static int findIndex(ArrayList treeAim, Tree tree) {
		Tree treeF = null;
		int parentIndex = -1;

		// 看该元素的父元素有没有排
		for (int i = 0; i < treeAim.size(); i++) {
			treeF = (Tree) treeAim.get(i);
			if (tree.getParentId().longValue() == treeF.getId().longValue()) {
				parentIndex = i;
				break;
			}
		}

		// 如果parentIndex=-1则该元素的父元素没有排，那么先不对该元素排序
		int Index = -1;
		if (parentIndex != -1) {
			Index = treeAim.size();
			Tree treeM = null;
			for (int i = parentIndex + 1; i < treeAim.size(); i++) {
				treeM = (Tree) treeAim.get(i);
				if (treeM.getArrange().longValue() == tree.getArrange()
						.longValue()) {

					if (treeM.getParentId().longValue() == tree.getParentId()
							.longValue()) {

						if (treeM.getSeq().longValue() > tree.getSeq()
								.longValue()) {
							Index = i;
							break;
						}
					}
				} else if (treeM.getArrange().longValue() < tree.getArrange()
						.longValue()) {
					Index = i;
					break;
				}
			}
		}

		return Index;
	}

	// 把ArrayList中的对象转成Tree对象
	private static void changeToTree(ArrayList treeList) {
		for (int i = 0; i < treeList.size(); i++) {
			Object o = treeList.get(i);
			Tree t = new Tree();
			t.setObject(o);

			try {
				Object id = PropertyUtils.getProperty(o, "id");
				if (null != id) {
					PropertyUtils.setProperty(t, "id", id);
				}
			} catch (Exception e) {
			}

			try {
				Object parent = PropertyUtils.getProperty(o, "parent");
				if (null != parent) {
					Object parentId = PropertyUtils.getProperty(parent, "id");
					if (null != parentId) {
						PropertyUtils.setProperty(t, "parentId", parentId);
					}
				}
			} catch (Exception e) {
			}

			treeList.set(i, t);
		}
	}

	// 对ArrayList做点相应的初始化处理
	private static void init(ArrayList treeList) {
		changeToTree(treeList);
		Tree tree = null;
		for (int i = 0; i < treeList.size(); i++) {
			tree = (Tree) treeList.get(i);
			if (tree.getParentId() == null
					|| tree.getParentId().longValue() == tree.getId()
							.longValue()) {
				tree.setParentId(new Long(-1));
				tree.setArrange(new Long(1));
				tree.setSeq(new Long(-1));
			}
		}

		// 判断是否有根节点，如果没有则将二级节点设成根节点
		boolean findParentId = true;
		for (int i = 0; i < treeList.size(); i++) {
			tree = (Tree) treeList.get(i);
			findParentId = false;

			Tree treeF = null;
			if (tree.getParentId().longValue() != -1) {

				for (int n = 0; n < treeList.size(); n++) {
					treeF = (Tree) treeList.get(n);
					if (tree.getParentId() == treeF.getId()) {
						findParentId = true;
						break;
					}

				}

				if (findParentId == false) {
					tree.setParentId(new Long(-1));
					tree.setArrange(new Long(1));
				}

			}
		}

		// 给元素加个顺序的id号
		for (int i = 0; i < treeList.size(); i++) {
			tree = (Tree) treeList.get(i);
			tree.setSeq(new Long(i));
		}

		while (!allArrange(treeList)) {
			for (int i = 0; i < treeList.size(); i++) {
				tree = (Tree) treeList.get(i);
				if (tree.getArrange() == null) {
					tree.setArrange(findArrage(treeList, tree));
				}
			}
		}
	}

	// 找出元素的层次关系
	private static Long findArrage(ArrayList treeList, Tree tree) {
		Tree treeF = null;
		for (int i = 0; i < treeList.size(); i++) {
			treeF = (Tree) treeList.get(i);
			if (tree.getParentId().longValue() == treeF.getId().longValue()) {
				if (treeF.getArrange() != null) {
					return new Long(treeF.getArrange().longValue() + 1);
				}
			}
		}
		return null;
	}

	// 判断是否所用的元素的层次关系都有值
	private static boolean allArrange(ArrayList treeList) {

		Tree tree = null;
		for (int i = 0; i < treeList.size(); i++) {
			tree = (Tree) treeList.get(i);
			if (tree.getArrange() == null) {
				return false;
			}
		}
		return true;
	}

}